Задачі лінійної алгебри. Розв’язування системи лінійних алгебраїчних рівнянь (ЛАР) типу А · х = b (1)
– матриця коефіцієнтів при невідомих;
– вектор-стовпчик невідомих;
– вектор-стовпчик вільних членів. В розгорнутому вигляді цю систему можна записати так: a11х1 + а12х2 + … + а1nxn = b1 a21х1 + а22х2 + … + а2nxn = b2 (2) … … … … … … … … … … … an1х1 + аn2х2 + … + аnnxn = bn Розв’язком системи рівнянь є вектор Х = (х1, х2, …, хn)T , елементами котрого є корені рівняння системи (2), що виражаються у вигляді лінійних функцій. Методи розв’язування систем лінійних алгебраїчних рівнянь. А · х = b Поділяються на дві групи : прямі та ітераційні. 1) Прямі методи – вони зводяться до кінцевих алгоритмів для обчислення коренів рівнянь (тобто розв’язки шукають за певними формулами). Вони дають розв’язки після виконання відомого для даного n (n – порядок) числа арифметичних операцій. Іншими словами, прямим методом розв’язування лінійної системи А·x = b називають будь-який метод, котрий дозволяє знайти елементи вектора x з допомогою скінченого числа елементарних математичних операцій: додавання, віднімання, ділення, множення, та, можливо, кореня квадратного. Оцінити ефективність будь-якого методу можна за допомогою двох – трьох важливих характеристик: числа операцій, необхідних для реалізації даного методу; об’єму пам’яті; чутливості до переносу похибок заокруглення (або обчислювальної стійкості). Розглянемо поняття стійкості методу. Нехай за значенням вхідної величини х шукається значення вихідної величини y. Якщо х має абсолютну похибку Δх, то розв’язок має похибку Δу. Метод називається стійким за вхідним параметром х, якщо малі похибки у вхідному параметрі х викликають малі похибки і в розв’язку у. Відсутність стійкості (нестійкий метод) означає, що навіть незначні похибки у вхідних даних ведуть до значних похибок в розв’язку, або до зовсім неправильного результату. Практично всі прямі методи розв’язування систем ЛАР базуються на зведені матриці А до матриці більш простішої структури – діагональної (тоді розв’язок очевидний) або трикутної – та методів розв’язування таких систем. До групи прямих методів належать: – метод Гауса та його різновиди: а) класичний метод Гауса із зведенням матриці А до верхньої трикутної матриці і одержанням розв’язків з допомогою обернених підстановок. Число операцій (вартість методу) – n2/2 операцій сумування, множення та n операцій ділення (можна ними знехтувати в порівнянні з n2/2) б) метод Гауса з вибором головного елемента (частковим або повним). Число арифметичних операцій при цьому складає ~ n3/3 сумувань та ~ n3/3 множень. Саме цим визначається повна вартість методу, оскільки вартість розв’язку вже самої трикутної системи незначна в порівнянні з вартістю зведення матриці до трикутного вигляду. – LU-розклад (lower-upper –нижній-верхній) А · х = b A = LU Ax = LUx = b Ly = b Ux = y Якщо використовувати алгоритм Краута, то число операцій складе
. З точки зору об’єму обчислень методу LU-розкладу еквівалентний методу Гауса з частковим вибором головного елемента його переваги – це можливість роботи з різними векторами вільних членів b та з транспонованими матрицями АТ (рівняння АТх = b – розв’язок знаходиться за тим же LU-розкладом). – метод Халецького (схема). При розкладі симетричних матриць можна зменшити число операцій і об’єм пам’яті. Повна вартість складає половині вартості методу Гауса + n обчислень квадратного кореня. Метод чисельно стійкий. – метод Жордана (роблять діагональну матрицю замість трикутної). Досить рідко використовується на практиці. До прямих методів відносяться також методи для кліткових та розріджених матриць. 2) Ітераційні (або наближені) методи – це методи послідовних наближень. В них необхідно задати деякий наближений розв’язок – так зване початкове наближення. Після цього з допомогою деякого алгоритму проводиться один цикл обчислень, котрий називається ітерацією...